from typing import *
from leetcode.editor.common.node import *


# leetcode submit region begin(Prohibit modification and deletion)
class NumMatrix(object):

    def __init__(self, matrix):
        m = len(matrix)
        n = len(matrix[0])
        self.preNums = [ [0]*(n+1) for _ in range(m+1)]
        for i in range(len(self.preNums)):
            for j in range(n+1):
                # 下边这句画个图自己理解
                self.preNums[i][j] = self.preNums[i-1][j] +self.preNums[i][j-1]-self.preNums[i-1][j-1]+matrix[i-1][j-1]

    def sumRegion(self, row1, col1, row2, col2):
        # 计算的是一个区域的和  肯定要这两个点围成一个矩阵的
        # 和所以我需要矩阵距离(0,0)最远点的位置和最近点的位置
        a = max(row1, row2)
        b = max(col1, col2)
        a1 = min(row1, row2)
        b2 = min(col1, col2)
        # preNums每个点的值都是 两个坐标-1的和 注意边界
        return self.preNums[a+1][b+1]-self.preNums[a+1][b2]- self.preNums[a1][b+1] + self.preNums[a1][b2]
        


# Your NumMatrix object will be instantiated and called as such:
# obj = NumMatrix(matrix)
# param_1 = obj.sumRegion(row1,col1,row2,col2)
# leetcode submit region end(Prohibit modification and deletion)


#if __name__ == '__main__':
#    solution = Solution()
    # your test code here